package main

import "fmt"

func main() {
	ln1 := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 4,
			Next: &ListNode{
				Val:  5,
				Next: nil,
			},
		},
	}

	ln2 := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 3,
			Next: &ListNode{
				Val:  4,
				Next: nil,
			},
		},
	}

	resultNode := merge(ln1, ln2)
	printListNode(resultNode)

}

func printListNode(node *ListNode) {
	for node != nil {
		fmt.Printf("-> %d ", node.Val)
		node = node.Next
	}
}

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	mid := len(lists) / 2
	left := mergeKLists(lists[:mid])
	right := mergeKLists(lists[mid:])
	return merge(left, right)
}

func merge(listNode1 *ListNode, listNode2 *ListNode) *ListNode {
	results := make([]int, 0)
	if listNode1 != nil && listNode2 != nil {
		if listNode1.Val < listNode2.Val {
			results = append(results, listNode1.Val)
			listNode1 = listNode1.Next
		} else {
			results = append(results, listNode2.Val)
			listNode2 = listNode2.Next
		}
	}

	for listNode1 != nil && listNode2 != nil {
		if listNode1.Val > listNode2.Val {
			results = append(results, listNode2.Val)
			listNode2 = listNode2.Next
		} else {
			results = append(results, listNode1.Val)
			listNode1 = listNode1.Next
		}
	}

	if listNode1 != nil {
		for listNode1 != nil {
			results = append(results, listNode1.Val)
			listNode1 = listNode1.Next
		}
	}

	if listNode2 != nil {
		for listNode2 != nil {
			results = append(results, listNode2.Val)
			listNode2 = listNode2.Next
		}
	}

	return build(results)
}

func build(results []int) *ListNode {
	if len(results) == 0 {
		return nil
	}

	tmp := &ListNode{
		Val:  results[0],
		Next: nil,
	}
	backup := tmp
	for i, result := range results {
		if i == 0 {
			continue
		}
		tmp.Next = &ListNode{
			Val:  result,
			Next: nil,
		}
		tmp = tmp.Next
	}
	return backup
}

type ListNode struct {
	Val  int
	Next *ListNode
}
